//给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。 
//
// 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "tree"
//输出: "eert"
//解释: 'e'出现两次，'r'和't'都只出现一次。
//因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
// 
//
// 示例 2: 
//
// 
//输入: s = "cccaaa"
//输出: "cccaaa"
//解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
//注意"cacaca"是不正确的，因为相同的字母必须放在一起。
// 
//
// 示例 3: 
//
// 
//输入: s = "Aabb"
//输出: "bbAa"
//解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
//注意'A'和'a'被认为是两种不同的字符。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 5 * 10⁵ 
// s 由大小写英文字母和数字组成 
// 
//
// Related Topics 哈希表 字符串 桶排序 计数 排序 堆（优先队列） 👍 470 👎 0


package leetcode.editor.cn;

import java.util.*;

/**
 * 根据字符出现频率排序
 * @date 2023-04-11 20:01:17
 */
class P451_SortCharactersByFrequency{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P451_SortCharactersByFrequency().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String frequencySort(String s) {
		char[] chars = s.toCharArray();
		HashMap<Character,Integer> map = new HashMap<>();
		for (char c : chars) {
			if(map.containsKey(c)){
				map.put(c,map.get(c)+1);
			}else {
				map.put(c,1);
			}
		}
		//使用桶排序
		//根据频率进行分桶
		List<Character>[] buckets = new ArrayList[s.length()+1];
		for (char c : map.keySet()) {
			int fre = map.get(c);
			if(buckets[fre] == null){
				buckets[fre] = new ArrayList<>();
			}
			buckets[fre].add(c);
		}
		List<Character> res = new ArrayList<>();
		for (int i = buckets.length-1; i >=0; i--) {//从后遍历桶
			if(buckets[i] == null)
				continue;
			for (int j = 0; j < buckets[i].size(); j++) {//遍历每个桶的元素
				for (int k = 0;k < i;k++){//加入桶的编号个字母
					res.add(buckets[i].get(j));
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (char c : res) {
			sb.append(c);
		}
		String result = sb.toString();
		return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
